/* 462. 最少移动次数使数组元素相等 II */
/**
 * @param {number[]} nums
 * @return {number}
 */
/* 暴力 */
var minMoves2 = function (nums) {
	const len = nums.length
	if (len < 2) return 0
	let ret = 0

	for (let i = 0; i < len; i++) {
		let _ret = 0
		for (let j = 0; j < len; j++) {
			if (nums[j] === nums[i]) continue
			if (!i) {
				ret += Math.abs(nums[j] - nums[i])
			} else {
				_ret += Math.abs(nums[j] - nums[i])
			}
		}
		if (i) {
			ret = Math.min(_ret, ret)
		}
	}
	return ret
}
/* 排序 */
var minMoves2 = function (nums) {
	nums.sort((a, b) => a - b)
	let n = nums.length,
		ret = 0,
		x = nums[Math.floor(n / 2)]

	for (let i = 0; i < n; i++) {
		ret += Math.abs(nums[i] - x)
	}
	return ret
}
const quickSelect = (nums, left, right, index) => {
	const q = randomPartition(nums, left, right)

	if (q === index) return nums[q]
	return q < index
		? quickSelect(nums, q + 1, right, index)
		: quickSelect(nums, left, q - 1, index)
}
/* 随机分区 */
const randomPartition = (nums, left, right) => {
	/* 随机取[left,right] 之间的数 */
	const i = Math.floor(Math.random() * (right - left + 1)) + left
	swap(nums, i, right)

	return partition(nums, left, right)
}
const partition = (nums, left, right) => {
	let x = nums[right],
		i = left - 1

	for (let j = left; j < right; j++) {
		if (nums[j] <= x) {
			swap(nums, ++i, j)
		}
	}
	swap(nums, i + 1, right)
	return i + 1
}
const swap = (nums, index1, index2) => {
	const temp = nums[index1]
	nums[index1] = nums[index2]
	nums[index2] = temp
}
var minMoves2 = function (nums) {
	let n = nums.length,
		ret = 0,
		x = quickSelect(nums, 0, n - 1, Math.floor(n / 2))
	console.log('x :>>', x)
}
const ret = minMoves2([1, 10, 2, 9])
console.log('minMoves2 :>>', ret)
